package DataStructrue.list;

import java.util.Iterator;
//双向链表
public class DLinkList<T>{
    private Node head;//头节点
    private Node tail;//最后一个节点
    private int N;//节点数量


    private class Node{
        public T obj;
        public Node pre;
        public Node next;
        public Node(T t,Node pre,Node next){
            this.obj=t;
            this.pre=pre;
            this.next=next;
        }
    }


    public DLinkList(){
        this.head=new Node(null,null,null);
        this.tail=null;
        this.N=0;
    }
    //清空
    public void clear(){
        this.head.pre=null;
        this.head.obj=null;
        this.tail=null;
        this.N=0;
    }
    //求链表长度
    public int length(){
        return N;
    }
    //判空
    public boolean isEmpty(){
        return N==0;
    }
    //获取第一个节点
    public T getFirst(){
        if(isEmpty())
            return null;
        return head.next.obj;
    }
    //获取最后一个节点
    public T getLast(){
        if(isEmpty())
            return null;
        return tail.obj;
    }
    //在指定位置插入节点
    public void insert(int i,T t){
        Node pre=head;
        for (int j = 0; j < i; j++) {
            pre=pre.next;
        }
        Node next=pre.next;
        Node nnode=new Node(t,pre,next);
        pre.next=nnode;
        next.pre=nnode;
        N++;
    }
    //查询指定位置节点
    public T get(int i){
        Node cur=head.next;
        for (int j = 0; j < i; j++) {
            cur=cur.next;
        }
        return cur.obj;
    }
    //查询节点索引
    public int indexOf(T t){
        Node cur=head;
        for (int i = 0; i<N ; i++) {
            cur=cur.next;
            if(cur.obj.equals(t))
                return i;
        }
        return -1;
    }
    //删除指定位置节点
    public T remove(int i){
        Node pre=head;
        for (int j = 0; j < i; j++) {
            pre=pre.next;
        }
        Node tag=pre.next;
        Node next=tag.next;
        pre.next=next;
        next.pre=pre;
        N--;
        return tag.obj;
    }


}
